package com.chj.dfs.class04;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;

//https://mp.weixin.qq.com/s?__biz=MzU0ODMyNDk0Mw==&mid=2247487910&idx=1&sn=2670aec7139c6b98e83ff66114ac1cf7&chksm=fb418286cc360b90741ed54fecd62fd45571b2caba3e41473a7ea0934f918d4b31537689c664&scene=21#wechat_redirect
//https://leetcode-cn.com/problems/path-sum-ii/solution/3chong-fang-shi-jie-jue-2chong-ji-bai-liao-100de-2/
public class Code04_PathSum {

	public static class Node {
		public int value;
		public Node left;
		public Node right;

		public Node(int data) {
			this.value = data;
		}
	}

//	public static List<List<Integer>> ret = new LinkedList<List<Integer>>();
//	public static Deque<Integer> path = new LinkedList<Integer>();

	public static List<List<Integer>> pathSum01(Node root, int sum, Deque<Integer> path, List<List<Integer>> ret) {
		ret = dfs(root, sum, path, ret);
		return ret;
	}

	public static List<List<Integer>> dfs(Node root, int sum, Deque<Integer> path, List<List<Integer>> ret) {
		if (root == null) {
			return ret;
		}
		path.offerLast(root.value);
		sum -= root.value;
		if (root.left == null && root.right == null && sum == 0) {
			ret.add(new ArrayList<Integer>(path));
		}
		ret = dfs(root.left, sum, path, ret);
		ret = dfs(root.right, sum, path, ret);
		path.pollLast();
		return ret;
	}

//	List<List<Integer>> ret = new LinkedList<List<Integer>>();
//	Map<Node, Node> map = new HashMap<Node, Node>();

	public static List<List<Integer>> pathSum02(Node root, int sum, Map<Node, Node> map, List<List<Integer>> ret) {
		if (root == null) {
			return ret;
		}

		Queue<Node> queueNode = new LinkedList<Node>();
		Queue<Integer> queueSum = new LinkedList<Integer>();
		// 安全的添加操作，在尾部添加
		queueNode.offer(root);
		queueSum.offer(0);

		while (!queueNode.isEmpty()) {
			// 获取第一个，同时删除它
			Node node = queueNode.poll();
			int rec = queueSum.poll() + node.value;

			if (node.left == null && node.right == null) {
				if (rec == sum) {
					getPath02(node, map, ret);
				}
			} else {
				if (node.left != null) {
					map.put(node.left, node);
					queueNode.offer(node.left);
					queueSum.offer(rec);
				}
				if (node.right != null) {
					map.put(node.right, node);
					queueNode.offer(node.right);
					queueSum.offer(rec);
				}
			}
		}

		return ret;
	}

	public static List<List<Integer>> getPath02(Node node, Map<Node, Node> map, List<List<Integer>> ret) {
		List<Integer> temp = new LinkedList<Integer>();
		while (node != null) {
			temp.add(node.value);
			node = map.get(node);
		}
		Collections.reverse(temp);
		ret.add(new ArrayList<Integer>(temp));
		return ret;

	}

	public static List<List<Integer>> pathSum03(Node root, int sum) {
		List<List<Integer>> result = new ArrayList<>();
		result = dfs(root, sum, new ArrayList<>(), result);
		return result;
	}

	public static List<List<Integer>> dfs(Node root, int sum, List<Integer> list, List<List<Integer>> result) {
		// 如果节点为空直接返回
		if (root == null) {
			return result;
		}
		// 因为list是引用传递，为了防止递归的时候分支污染，我们要在每个路径
		// 中都要新建一个subList
		List<Integer> subList = new ArrayList<>(list);
		// 把当前节点值加入到subList中
		subList.add(new Integer(root.value));
		// 如果到达叶子节点，就不能往下走了，直接return
		if (root.left == null && root.right == null) {
			// 如果到达叶子节点，并且sum等于叶子节点的值，说明我们找到了一组，
			// 要把它放到result中
			if (sum == root.value) {
				result.add(subList);
			}
			// 到叶子节点之后直接返回，因为在往下就走不动了
			return result;
		}
		// 如果没到达叶子节点，就继续从他的左右两个子节点往下找，注意到
		// 下一步的时候，sum值要减去当前节点的值
		dfs(root.left, sum - root.value, subList, result);
		return dfs(root.right, sum - root.value, subList, result);
	}

	public static void printTree(Node head) {
		System.out.println("Binary Tree:");
		printInOrder(head, 0, "H", 17);
		System.out.println();
	}

	public static void printInOrder(Node head, int height, String to, int len) {
		if (head == null) {
			return;
		}
		printInOrder(head.right, height + 1, "v", len);
		String val = to + head.value + to;
		int lenM = val.length();
		int lenL = (len - lenM) / 2;
		int lenR = len - lenM - lenL;
		val = getSpace(lenL) + val + getSpace(lenR);
		System.out.println(getSpace(height * len) + val);
		printInOrder(head.left, height + 1, "^", len);
	}

	public static String getSpace(int num) {
		String space = " ";
		StringBuffer buf = new StringBuffer("");
		for (int i = 0; i < num; i++) {
			buf.append(space);
		}
		return buf.toString();
	}

	public static void printArray(List<List<Integer>> vec) {
		if (vec == null) {
			return;
		}
		for (int i = 0; i < vec.size(); i++) {
			System.out.print(vec.get(i) + " ");
		}
		System.out.println();
	}

	public static void main(String[] args) {
		Node head = new Node(5);
		head.left = new Node(4);
		head.right = new Node(8);
		head.left.left = new Node(11);
		head.right.left = new Node(13);
		head.right.right = new Node(4);
		head.right.right.right = new Node(1);
		head.right.right.left = new Node(5);
		head.left.left.left = new Node(7);
		head.left.left.right = new Node(2);
		printTree(head);

//		System.out.println(hasPathSum(head, 22));
//		System.out.println(hasPathSum02(head, 22));
//		System.out.println(hasPathSum03(head, 22));
//		System.out.println(hasPathSum04(head, 22));
//		System.out.println(hasPathSum05(head, 22));

//		List<List<Integer>> ret = new ArrayList<List<Integer>>();
//		Deque<Integer> path = new LinkedList<Integer>();
//
//		List<List<Integer>> res = pathSum01(head, 22, path, ret);
//		printArray(res);

//		List<List<Integer>> ret02 = new ArrayList<List<Integer>>();
//		Map<Node, Node> map02 = new HashMap<Node, Node>();
//
//		List<List<Integer>> res = pathSum02(head, 22, map02, ret02);
//		printArray(res);

//		List<List<Integer>> ret = new ArrayList<List<Integer>>();
//		Deque<Integer> path = new LinkedList<Integer>();
//
		List<List<Integer>> res = pathSum03(head, 22);
		printArray(res);
	}

//	[
//	   [5,4,11,2],
//	   [5,8,4,5]
//	]

}
